// 最大子数组问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// #define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

const int MAX_ARRAY_SIZE = 1000000;
const int MAX_NUM_ABS = 10000;

int MaxSubsequeceSum_First(int array[], int n);
int MaxSubsequeceSum_Second(int array[], int n);
int MaxSubsequeceSum_Third(int array[], int left, int right);
int MaxSubsequeceSum_Forth(int array[], int n);
int main()
{
	int size, * array, answer = 0;
	printf("请输入小于1,000,000的数作为随机数组大小：\n");
	scanf("%d", &size);
	if (size > MAX_ARRAY_SIZE)
	{
		printf("输入错误");
		return 1;
	}
	array = (int*)malloc(size * sizeof(int));
	printf("生成数组：");
	for (int i = 0; i <= size - 1; i++) {
		array[i] = 2 * (rand() % MAX_NUM_ABS) - MAX_NUM_ABS;
		printf("%d ", array[i]);
	}
	clock_t start, finish;
	double totaltime;
	start = clock();
	// answer = MaxSubsequeceSum_First(array, size);
	// answer = MaxSubsequeceSum_Second(array, size);
	// answer = MaxSubsequeceSum_Third(array, 0, size - 1);
	// answer = MaxSubsequeceSum_Forth(array, size);
	finish = clock();
	totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("运行结果：%d\t\t\t运行时间：%lf\n", answer, totaltime);
	free(array);
	return 0;
}
int MaxSubsequeceSum_First(int array[], int n)
{
	int maxsum = 0;
	for (int i = 0; i <= n - 1; i++)
	{
		for (int j = i; j <= n - 1; j++)
		{
			int thissum = 0;
			for (int k = i; k <= j; k++)
				thissum = thissum + array[k];
			if (thissum > maxsum)
				maxsum = thissum;
		}
	}
	return maxsum;
}
int MaxSubsequeceSum_Second(int array[], int n)
{
	int maxsum = 0;
	for (int i = 0; i <= n - 1; i++)
	{
		int thissum = 0;
		for (int j = i; j <= n - 1; j++)
		{
			thissum = thissum + array[j];
			if (thissum > maxsum)
				maxsum = thissum;
		}
	}
	return maxsum;
}
int MaxSubsequeceSum_Third(int array[], int left, int right)
{
	int sum = 0, leftsum = 0, rightsum = 0, rightanswer = 0, leftanswr = 0, n = right - left + 1;
	if (n <= 0)
		return 0;
	for (int i = left + n / 2 - 1, a = 0; i >= left; i--)
	{
		a = array[i] + a;
		if (a > leftsum)
			leftsum = a;
	}
	for (int i = left + n / 2, a = 0; i <= right; i++)
	{
		a = array[i] + a;
		if (a > rightsum)
			rightsum = a;
	}
	sum = leftsum + rightsum;
	leftanswr = MaxSubsequeceSum_Third(array, left, left + n / 2 - 1);
	rightanswer = MaxSubsequeceSum_Third(array, left + n / 2 + 1, right);
	if (sum > leftanswr && sum > rightanswer)
		return sum;
	else if (leftanswr > rightanswer)
		return leftanswr;
	else
		return rightanswer;
}
int MaxSubsequeceSum_Forth(int array[], int n)
{
	int maxsum = 0, thissum = 0;
	for (int i = 0; i <= n - 1; i++)
	{
		thissum = thissum + array[i];
		if (thissum > maxsum)
			maxsum = thissum;
		if (thissum < 0)
			thissum = 0;
	}
	return maxsum;
}
